1. Technical Field
The present invention relates in general to combined routing and switching devices in computer networks and in particular to such devices in local area network and wide area network environments. Still more particularly, the present invention relates to improving performance of combined routing and switching devices used in local area networks and wide area networks by providing a cut-through.
2. Description of the Related Art
The past decade has seen an explosion in the use of computer networks in all sectors of society: business and industry, education and research, and even recreation. This growth in the use of computer networks has been accompanied by a proportional demand for improvement of the performance of such networks.
Computer networks are classified by their geographic scope. The most commonly used terms for classifying computer networks are local area network (LAN) and wide area network (WAN). LANs are generally limited to computers within a relatively small area, such as a building, office or campus. WANs, on the other hand, connect computers over larger geographic scopes, such as from one city to another. Less commonly used terms for classifying computer networks include metropolitan area network (MAN) and global area network (GAN), which have self-explanatory geographic scopes. Currently the Internet is the most prominent example of a global area network.
Various technologies have evolved for communications and/or data transmission in computer networks, including Ethernet, token ring, fiber distributed data interface (FDDI), and asynchronous transfer mode (ATM). Data transmission within and between networks using such technologies are governed by various protocols, such as frame relay (FR), X.25, integrated services digital network (ISDN), media access control address protocol, and transmission convergence protocol/internet protocol (TCP/IP).
As with other forms of digital communications, data in computer networks is commonly transmitted in packets or frames, i.e.--discrete bundles of data. Frames are comprised of various fields, such as header, address, data, and control fields. The arrangement or format of these fields within a frame is protocol-dependent. An explanation of some frame formats commonly used in computer networks may be found in Internet Engineering Task Force (IETF) Request for Comments (RFC) 1490, which is incorporated herein by reference. However, it will be understood by those skilled in the art that RFC 1490 is not exhaustive of all frame formats currently in use.
A given communications or data transmission process in a network often requires delivery of multiple packets or frames of data from a source to a destination within the network. For example, retrieval of a file using file transfer protocol (FTP) will generally be accomplished using a large number of frames. Although relating to the same process (i.e., FTP), different frames may be transmitted via different paths within the network. As used herein, a data flow refers to a sequence of related frames sent from a particular source to a particular destination within the network.
Various devices exist for transmitting packets or frames of data within a network or between networks. A bridge or gateway--the terms are often used interchangeably--passes frames of data from one network to another, the two networks typically being local area networks. FIG. 1 illustrates a bridge connecting two token ring LANs, while FIG. 2 depicts a bridge linking an Ethernet LAN to a token ring LAN. Bridges store and forward frames of data, looking only at the low-level addressing and not at the frame's internal data to determine where the frames are sent.
Routers are an evolution beyond bridges, usually routing frames of data at a higher level protocol than is handled by bridges. The oldest routers were internet protocol (IP) routers, but other protocols may be routed including InterPacketExchange (IPX) by Novell, Inc. and high performance routing (HPR) by International Business Machines Corporation of Armonk, N.Y. Like bridges, routers store and forward frames. However, a router, after storing a frame of data, looks into the internal data of the frame for higher protocol information regarding the ultimate destination of the frame. A router then consults an internal table of available paths to the ultimate destination and corresponding protocols supported by those paths, and makes a decision regarding how to route the frame to its ultimate destination.
If a router encounters a frame of data not fitting into the list of protocols which it routes, it bridges the frame. Routers will attempt to route first, then bridge. As shown in FIG. 3, which illustrates an example of a router, a router usually has more than two connections to disparate LANs or WANs. Routers may also be required to interface between multiple protocols.
A switch is a hardware device providing physical connection within or between different networks. Unlike bridges and routers, a switch typically forwards data without first storing the entire frame. The delays inherent in storing the entire frames before forwarding are thus eliminated. A switch transmits the data bits of the frame received from the source port directly to the destination port as soon as the destination is ascertained. Switches are often used as part of virtual circuits (VCs), or defined paths between a given source or destination. A virtual circuit may be either a switched virtual circuit (SVC) or a permanent virtual circuit (PVC). Switched virtual circuits are transient, set up for the benefit of a given process or data flow, and may result in different paths being used between the same source and destination for discrete processes. Permanent virtual circuits (PVCs) are defined paths between a source and destination using designated nodes in a predetermined sequence.
Switches were first used in telephone networks and other WANs. In WAN environments, for example, Frame Relay and ATM protocols are capable of using switches. FIG. 4 depicts an example of a WAN using Frame Relay switches to connect LANs. Routers within the LANs which connect the LAN to the WAN must have Frame Relay Access Devices (FRAD) attached.
Despite their origins in the WAN environment, switches are beginning to be used in LAN implementations. To improve high-demand, high-bandwidth data delivery, the network industry is attempting to overcome latency (delay) in routers by going to switching technologies. LAN technologies such as Ethernet and token ring have been adapted to use switches. ATM, which may operate through switches, works in either LAN or WAN environments. FIG. 5 illustrates an example of a switch in a network LAN environment. FIGS. 6 and 7 depict examples of Ethernet and token ring switches, respectively.
As switching is implemented in LAN environments, LAN connections have moved from shared access transport (SAT) sharing of media to connecting directly to switch ports. The LAN framing remains unchanged, but data flows attempt to pass or "cut through" the switch. Cut through avoids completely storing the frame before forwarding it, passing through the bits as soon as the destination port is known. Adaptive cut through is a variation which seeks to avoid wasting frames if the destination port is already busy by storing the frame in the switch until the destination is available.
The current trend in network implementation is to use both routing and switching together at a network node. Products are being developed which combine routers--especially IP routers--with switches. However, although physically combined in a single package for use at network nodes, functional combination of routers and switches has been limited. Generally routers in such combined packages communicate with the network through the switches, but routing and switching technologies are not being used synergistically in networks to take full advantage of both technologies. For example, a need exists for a method of using routing at the beginning of certain network data flows, then changing over to switching to improve data throughput by removing routing latency. This need exists in all LAN-to-LAN, LAN-to-WAN, and WAN-to-WAN connections.